#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=1e5+5;
int n,K;
int a[Maxn],pr[Maxn][6];
int las[Maxn][6];

struct node{
	int mn,cnt;
	inline node operator+(const node&b)const{
		if(mn==b.mn)return (node){mn,cnt+b.cnt};
		if(mn<b.mn)return (node){mn,cnt};
		return b;
	}
};

struct Tree{
	int tag;
	node val;
}t[Maxn<<2];

void build(int x,int l,int r){
	t[x].tag=0;if(l==r)return void(t[x].val={0,1});
	int mid=l+r>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	t[x].val=t[x<<1].val+t[x<<1|1].val;
}
inline void add_(int x,int p){
	t[x].tag+=p;t[x].val.mn+=p;
}
inline void spread(int x){
	if(!t[x].tag)return;
	add_(x<<1,t[x].tag);
	add_(x<<1|1,t[x].tag);
	t[x].tag=0;
}
void change(int x,int l,int r,int L,int R,int p){
	if(L>R)return;
	if(L<=l&&r<=R)return void(add_(x,p));
	int mid=l+r>>1;spread(x);
	if(mid>=L)change(x<<1,l,mid,L,R,p);
	if(mid<R)change(x<<1|1,mid+1,r,L,R,p);
	t[x].val=t[x<<1].val+t[x<<1|1].val;
}




inline ll calc(int s){
	ll res=0;build(1,1,n);
	for(int i=1;i<=n;i++){
		for(int k=0;k<=K;k++){
			if(s>>k&1)change(1,1,n,pr[i][k]+1,(k==0?i:pr[i][k-1]),1);//,printf("add:[%d,%d,1]\n",pr[i][k]+1,(k==0?i:pr[i][k-1]));
			if(k&&(s>>k-1&1))change(1,1,n,pr[i][k]+1,pr[i][k-1],-1);//,printf("add:  %d  [%d,%d,-1]\n",i,pr[i][k]+1,pr[i][k-1]);
		}
		
		res+=n-t[1].val.cnt*(t[1].val.mn==0);
//		printf("fwefwe %d %d\n",i,n-t[1].val.cnt);
	}return res;
}
int main(){
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	n=read();K=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		pr[i][0]=las[a[i]][0];pr[i][1]=las[a[i]][1];
		pr[i][2]=las[a[i]][2];pr[i][3]=las[a[i]][3];
		pr[i][4]=las[a[i]][4];
		las[a[i]][4]=las[a[i]][3];
		las[a[i]][3]=las[a[i]][2];las[a[i]][2]=las[a[i]][1];
		las[a[i]][1]=las[a[i]][0];las[a[i]][0]=i;
		
//		printf("gfoeiheoifhwioufhwi %d %d %d\n",a[i],las[a[i]][0],pr[i][0]);
	}
	ll ans=0;
	for(int s=1;s<(1<<K);s++)ans+=(__builtin_popcount(s)&1?1:-1)*calc(s);
	printf("%lld\n",ans);
	return 0;
}
/*
3 1
1 2 1

6 2
5 4 5 2 6 5
*/
